快速排序
快速排序
基本思想
- 通过一趟排序将要排序的序列分割成独立的两部分
- 其中一部分的所有数据都比另一部分的所有数据都要小
- 再按此方法对两部分分别进行快速排序
- 最终达到整个数据序列有序
流程
- 设定一个分界值,通过该分界值将数组分成左右两部分
- 将大于或等于分界值的数据集中到数组右边,小于分界值的集中到数组左边
- 然后,左边和右边的数据独立排序,对于左侧的数组数据,又可以取一个分界值,将该部分的数据分成左右两部分,同样左边放置较小值,右边放置较大值。右侧的数组也做类似处理
- 重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序,再递归将右侧部分排好序。当左右两个部分数据都排序完成后,整个数组的排序也就完成了。
第一次选取5为分界值
第二次 右边选择6,左边选择3为分界值
第三次 左1选择2,右1选择4 右2选择7作为分界值
第四次右选择9作为分界值
代码实现:
def quick_sort(alist, start, end):
"""快速排序"""
# 递归的结束条件
if start >= end:
return
# 界限值
mid = alist[start]
# 左右游标
left = start
right = end
while left < right:
# 从右边开始找寻小于mid的值,归类到左边
while alist[right] >= mid and left < right:
right -= 1
alist[left] = alist[right]
# 从左边边开始找寻大于mid的值,归类到右边
while alist[left] < mid and left < right:
left += 1
alist[right] = alist[left]
# 循环一旦结束了,证明找到了mid应该在的位置
alist[left] = mid
# 递归操作
quick_sort(alist, start, left - 1)
quick_sort(alist, right + 1, end)
if __name__ == '__main__':
alist = [1, 2, 100, 50, 1000, 1, 1]
quick_sort(alist, 0, len(alist) - 1)
print(alist)
Java版实现
public class QickSortTest {
public static void main(String[] args) {
int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right){ // left 为红色箭头,right为蓝色箭头
// 递归结束条件
if(right < left){
return;
}
int left0 = left; //0
int right0 = right; //9
// 计算出基准
int baseNumber = arr[left0]; // arr[0]
while (left != right){
// 1. 从右开始查找比基准数小的
while (arr[right] >= baseNumber && right > left){
right--;
}
//2. 从左开始查找比基准数大的
while (arr[left] <= baseNumber && right > left){
left++;
}
// 3. 交换两个值的位置
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
// 基准归位
int temp = arr[left];
arr[left] = arr[left0];
arr[left0] = temp;
// 递归调用自己,将左边排好
quickSort(arr, left0, left - 1);
// 递归调用自己,将右边排好
quickSort(arr, left+1, right0);
}
}
快速排序的稳定性
最差时间复杂度:
最优时间复杂度:
快速排序是一个不稳定算法。